package com.study.lintcode.my.code_10;

import java.util.*;

/**********************************************************************
 * &lt;p&gt;文件名：Example_1.java &lt;/p&gt;
 * &lt;p&gt;文件描述：(https://www.lintcode.com/problem/a-b-problem/)
 * @project_name：LintCode
 * @author zengshunyao
 * @create 2019/1/5 21:56
 * @history
 * @department：政务事业部
 * Copyright ChengDu Funi Cloud Code Technology Development CO.,LTD 2014
 *                    All Rights Reserved.
 */
public class Example_10 {
    public int count = 0;

    /*
     * @param str: A string
     * @return: all permutations
     */
    public List<String> stringPermutation(String str) {
        // write your code here
        List<String> result = new ArrayList<String>();
        if (str == null || str.length() == 0) {
            result.add("");
            return result;
        }

        //Sort Array beforehand for ordering purpose
        str = sortString(str);

        Set<String> set = new HashSet<String>();

        // 1.递归求解
        dfs(str.toCharArray(), 0, str.length(), set);

        result.addAll(new LinkedList<String>(set));

        return result;
    }


    /**
     * 递归求解
     *
     * @param originalChars
     * @param begin
     * @param end
     * @param result
     */
    private void dfs(char[] originalChars,
                     int begin,
                     int end,
                     Set<String> result) {
        count++;
        if (begin == originalChars.length - 1) {

            print(begin);

            System.out.println(begin + "," + begin + "->" + Arrays.toString(originalChars));

            result.add(new String(originalChars));
            return;
        }

        for (int i = begin; i < end; i++) {
            //去掉重复
            if (is_swap(originalChars, i, begin)) {

                print(begin);

                System.out.println(begin + "," + i + "->" + Arrays.toString(originalChars));

                swap(originalChars, i, begin);
                dfs(originalChars, begin + 1, end, result);
                swap(originalChars, i, begin);
            }
        }
    }

    private boolean is_swap(char[] chars, int i, int index) {
        for (int k = i; k < index; k++) {
            if (chars[index] == chars[k]) {
                return false;
            }
        }
        return true;
    }

    private void swap(char[] chars, int i, int j) {
        char ch = chars[i];
        chars[i] = chars[j];
        chars[j] = ch;
    }

    private String sortString(String str) {
        char[] tempArray = str.toCharArray();
        Arrays.sort(tempArray);
        return new String(tempArray);
    }

    public void print(int num) {
        for (int j = 0; j < num; j++) {
            System.out.print("-");
        }
    }

    public static void main(String[] args) {
//        String originalStr = "alibaba";
        //alibaba
        //aaabbli
        //aaa->...
        //aaa...->bb...
        //li,il
        //bli,lbi,lib,  bil,ibl,ilb
        //bbli,bbli,blbi,blib,  blbi,lbbi,lbbi,lbib  blib,lbib,libb,libb,  ..............

        String originalStr = "abc";
        //a,b,c
        //bc,cb
        //abc->abc,bac,bca---acb,cab,bca

//        String originalStr = "abb";
        //abb->abb,bab,bba
        //bb
        Example_10 example_10 = new Example_10();
        List<String> stringList = example_10.stringPermutation(originalStr);
        System.out.println("共" + stringList.size() + "个");

//        for (String s : stringList) {
//            System.out.println(s);
//        }

        System.out.println(Arrays.toString(stringList.toArray()));
        System.out.println("递归次数：" + example_10.count);
        System.out.println(Math.pow(3, 3));
    }
}
